/**
 * <vendor>
 *  Copyright 2009 Quanben Tech.
 * </vendor>
 */

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using QSharp.String.Compiler;


namespace QSharp.String.Rex
{
    public interface IContinuous<T> : IComparable<T>
    {
        bool IsAdjacentTo(T that);
        bool IsSucceeding(T that);
        bool IsPreceding(T that);
    }

    interface IContinuousToken : IContinuous<IContinuousToken>, IComparableToken
    {
    }

    public class SegmentedSet<T> : IEnumerable<SegmentedSet<T>.Range> where T : IContinuous<T>
    {
    /* types */

        public class Range
        {
            public T Low;
            public T High;   // zero for infinity

            public Range(T low, T high) { Low = low; High = high; }

            public int CompareTo(T t)
            {
                if (t.CompareTo(Low) < 0) return 1;
                if (t.CompareTo(High) > 0) return -1;
                return 0;
            }

            public override string ToString()
            {
                return "[" + Low.ToString() + ", " + High.ToString() + "]";
            }
        }

    /* data */

        protected List<Range> mData = new List<Range>();

    /* methods */

        protected bool Find(T t, out int m)
        {   // TODO: to be tested
            m = 0;
            int n = mData.Count;
            if (n == 0) return false;
            int left = 0, right = n;
            while (left < right)
            {
                m = (left + right) / 2;
                int cmp = mData[m].CompareTo(t);
                if (cmp == 0) return true;
                if (cmp < 0) left = m + 1;
                else right = m;
            }
            m = left;
            return false;
        }

        protected void TryMerge(int left, int right)
        {
            if (mData[left].High.IsAdjacentTo(mData[right].Low))    /* IsPreceding */
            {
                mData[left].High = mData[right].High;
                mData.RemoveAt(right);
            }
        }

        protected void TryInsert(int p, T low, T high)
        {
            if (p > 0 && mData[p - 1].High.IsAdjacentTo(low))       /* IsPreceding */
            {
                mData[p - 1].High = high;
                if (p < mData.Count && high.IsAdjacentTo(mData[p].Low))     /* IsPreceding */
                {
                    mData[p - 1].High = mData[p].High;
                    mData.RemoveAt(p);
                }
            }
            else if (p >= 0 && p < mData.Count && high.IsAdjacentTo(mData[p].Low))  /* IsPreceding */
            {
                mData[p].Low = low;
            }
            else
            {
                mData.Insert(p, new Range(low, high));
            }
        }

        protected void TryOverlay(int plow, int phigh, T low, T high)
        {
            if (plow > 0 && mData[plow - 1].High.IsAdjacentTo(low))     /* IsPreceding */   
            {
                if (phigh < mData.Count && high.IsAdjacentTo(mData[phigh].Low)) /* IsPreceding */
                {
                    mData[plow - 1].High = mData[phigh].High;
                    Remove(plow, phigh);
                }
                else
                {
                    mData[plow - 1].High = high;
                    Remove(plow, phigh - 1);
                }
            }
            else
            {
                mData[plow].Low = low;
                if (phigh < mData.Count && high.IsAdjacentTo(mData[phigh].Low)) /* IsPreceding */
                {
                    mData[plow].High = mData[phigh].High;
                    Remove(plow + 1, phigh);
                }
                else
                {
                    mData[plow - 1].High = high;
                    Remove(plow + 1, phigh - 1);
                }
            }
        }

        protected void Remove(int first, int last)
        {
            if (last < first)
            {
                return;
            }
            mData.RemoveRange(first, last - first + 1);
        }

        public void Add(T t)
        {
            AddRange(t, t);
        }

        public void AddRange(T low, T high)
        {
            int plow, phigh;
            bool lowfound = Find(low, out plow);
            bool highfound = Find(high, out phigh);

            if (plow == phigh)
            {
                // three possibilities: both found, only high found, neither found
                if (lowfound && highfound)
                {
                    return;
                }
                else if (highfound)
                {   // low not found
                    mData[plow].Low = low;
                    TryMerge(plow - 1, plow);
                }
                else
                {   // neither was found
                    TryInsert(plow, low, high);
                }
            }
            else    // plow < phigh
            {
                if (lowfound && highfound)
                {
                    mData[plow].High = mData[phigh].High;
                    Remove(plow + 1, phigh);
                }
                else if (lowfound)
                {   // high not found

                    if (phigh < mData.Count && mData[phigh].Low.IsAdjacentTo(high)) /* IsPreceding */
                    {
                        mData[plow].High = mData[phigh].High;
                        Remove(plow + 1, phigh);
                    }
                    else
                    {
                        mData[plow].High = high;
                        Remove(plow + 1, phigh - 1);
                    }
                }
                else if (highfound)
                {   // low not found
                    if (plow > 0 && mData[plow - 1].High.IsAdjacentTo(low)) /* IsPreceding */
                    {
                        mData[plow - 1].High = mData[phigh].High;
                        Remove(plow, phigh);
                    }
                    else
                    {
                        mData[plow].Low = low;
                        mData[plow].High = mData[phigh].High;
                        Remove(plow + 1, phigh);
                    }
                }
                else
                {   // neither was found
                    TryOverlay(plow, phigh, low, high);
                }
            }
        }

        public bool Contains(T t)
        {
            int dummy;
            return Find(t, out dummy);
        }

        public bool IsEmpty
        {
            get 
            {
                return mData.Count == 0;
            }
        }

        public Range this[int i]
        {
            get
            {
                if (i >= mData.Count) throw new IndexOutOfRangeException();
                return mData[i];
            }
        }

        public int SegmentCount
        {
            get
            {
                return mData.Count;
            }
        }

        public IEnumerator<Range> GetEnumerator()
        {
            foreach (Range range in mData)
            {
                yield return range;
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            foreach (Range r in mData)
            {
                if (sb.Length > 0)
                {
                    sb.Append(" + ");
                }
                sb.Append(r.ToString());
            }
            return sb.ToString();
        }
    }   /* class SegmentedSet */

#if TEST_String_Compiler_Rex_SegmentedSetTest
    class SegmentedSetTest
    {
        struct Continuous : IContinuous<Continuous>
        {
            public int Value;

            public Continuous(int v) { Value = v; }

            public int CompareTo(IContinuous that)
            {
                if (!(that is Continuous))
                {
                    throw new ArgumentException();
                }
                return CompareTo((Continuous)that);
            }

            public bool IsAdjacentTo(IContinuous that)
            {
                if (!(that is Continuous))
                {
                    throw new ArgumentException();
                }
                return IsAdjacentTo((Continuous)that);
            }

            public int CompareTo(Continuous that)
            {
                return Value.CompareTo(that.Value);
            }

            public bool IsAdjacentTo(Continuous that)
            {
                return (Value==that.Value+1 || Value+1==that.Value);
            }

            public static implicit operator Continuous (int v)
            {
                return new Continuous(v);
            }

            public override string ToString()
            {
                return Value.ToString();
            }
        }

        static void Test()
        {
            try
            {
                int iTest = 0;
                int nTests = 10;
                Random rand = new Random();
                int len = 10;
                int slen = 200;
                
                SegmentedSet<Continuous> segset = new SegmentedSet<Continuous>();

                for (iTest = 0; iTest < nTests; iTest++)
                {
                    int rs = rand.Next();
                    int rl = rand.Next();
                    int s = rs % slen;
                    int l = rl % len;
                    segset.AddRange(s, s+l);
                    Console.WriteLine(": Adding range [{0}, {1}]", s, s+l);
                    Console.WriteLine(":  The result is {0}", segset);
                }
            }
            catch (Exception ex)
            {
                Console.WriteLine("Ex = {0}", ex);
            }
        }
    }   /* class SegmentedSetTest */
#endif  // if TEST_String_Compiler_Rex_SegmentedSetTest

}   /* namespace QSharp.String.Rex */
